package com.wc.alorithm_blue_bridge._数学知识.快速幂.Q1514;

import java.util.Scanner;

/**
 * @Author congge
 * @Date 2023/11/4 13:01
 * @description 快速幂
 * https://www.lanqiao.cn/problems/1514/learning/?page=1&first_category_id=1&sort=students_count&second_category_id=8
 */
public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int b = sc.nextInt();
        int p = sc.nextInt();
        int k = sc.nextInt();
        long ans = new Main().quick(b,p,k);
        System.out.println(ans);
    }

    public long quick(int b, int p, int k) {
        if (p == 1) {
            return b % k;
        }
        long sum = 1;

        long qk = quick(b, p / 2, k);
        sum = qk * qk % k;
        if (p % 2 == 1) {
            sum = sum * b % k;
        }
        return sum;
    }
}
